// hdu5772
// 题意：
// 给定一个长度为n(<=100)的数字字符串，现在对于一个子序列，你要计算一个score，
// score = value - total_cost
// value的计算如下，sigma(w[id[i]][id[j]])，(i != j) w是事先给好的权值矩阵，
// i, j是子序列对应下标i, j，id[i]表示的是子序列的下标i位置对应原始串的位置。
//
// total_cost是cost[i]的和，i是0~9每个数字，对于数字i，如果i在子序列没出现，
// 费用就是0, 如果i在子序列中出现了t次，cost[i]=ax*(t-1)+bx。
//
// 要求所有可能score中最大的score。
//
// 题解：
// 这个形式很像最大比和权图的形式，所以我们可以构出一个闭合全图，分三层，
// 第一层对于w[i][j]这个节点，权值为+w[i][j]，然后连边到i和j位置，
// 对于字符串每个位置i，权值是-ax[i]，然后连边到对应的数字节点上，
// 对于数字节点0~9权值为-(bx[i]-ax[i])。
//
// 因为cost[i]的形式可以改写成cost[i]=ax*t + bx-ax，这样，选中这位就要付出
// ax的代价，且如果这一位对应数字出现，也要有bx-ax的代价。
//
// 然后就是闭合全图的网络流构图，原图所有边都改成+oo的容量，源点s连向所有
// 正权一条容量为权值的边，所有负权连向汇点t容量为负权绝对值的边，
// 然后跑一便最小割，最后 所有正权值的和-最小割 就是闭合权图可以得道最大的
// 权值。
//
// 证明参考胡伯涛论文。
//
// ml:run = $bin < input
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <limits>

template <class T>
struct dinic
{
	typedef T value_type;
	typedef int size_type;
	typedef std::vector<size_type>::iterator edge_iter;

	struct edge {
		size_type from, to;
		value_type capacity, flow;
	};

	dinic(size_type num) : size(num)
	{
		graph.resize(num);	//[0, num)
		dist.resize(num);	//[0, num)
	}

	void add_edge(int u, int v, value_type cap = capacity_inf)
	{
		edge tmp;
		tmp.from = u; tmp.to = v; tmp.capacity = cap; tmp.flow = 0;
		edges.push_back(tmp);
		graph[u].push_back(edges.size() - 1);

		tmp.from = v; tmp.to = u; tmp.capacity = 0; tmp.flow = 0;
		edges.push_back(tmp);
		graph[v].push_back(edges.size() - 1);
	}

	bool bfs_label(size_type source, size_type target)
	{
		std::fill(dist.begin(), dist.end(), -1);
		std::queue<size_type> q;
		q.push(source);
		dist[source] = 0;
		while (!q.empty()) {
			size_type now = q.front();
			q.pop();
			for (edge_iter it = graph[now].begin(); it != graph[now].end(); ++it) {
				edge e = edges[*it];
				if (dist[e.to] == -1 && e.capacity > e.flow) {
					q.push(e.to);
					dist[e.to] = dist[now] + 1;
				}
			}
		}
		return dist[target] != -1;
	}

	value_type dfs(size_type v, size_type target, value_type f)
	{
		if (v == target || !f) return f;
		value_type block_flow = 0;
		for (edge_iter it = graph[v].begin(); it != graph[v].end(); ++it) {
			edge & e = edges[*it];
			if (e.capacity > e.flow && dist[e.to] == dist[v] + 1) {
				value_type tmp = dfs(e.to, target,
						std::min(e.capacity - e.flow, f - block_flow));
				block_flow += tmp;
				e.flow += tmp;
				edges[(*it) ^ 1].flow -= tmp;
			}
		}
		if (!block_flow) dist[v] = -1;
		return block_flow;
	}

	value_type max_flow(size_type source, size_type target)
	{
		value_type flow = 0;
		for (int tmp; bfs_label(source, target); )
			while ((tmp = dfs(source, target, capacity_inf))) flow += tmp;
		return flow;
	}

//private:
	value_type static const capacity_inf = std::numeric_limits<value_type>::max();
	size_type size;
	std::vector<int> dist;
	std::vector<edge> edges;
	std::vector<std::vector<size_type>> graph;
};


int const maxn = 200;
int w[maxn][maxn];
int ax[10], bx[10];
int n;
std::string str;

int main()
{
    std::ios_base::sync_with_stdio(false);
    int T; std::cin >> T;
    for (int ti = 1; ti <= T; ti++) {
        std::cout << "Case #" << ti << ": ";
        std::cin >> n >> str;
        for (int i = 0; i < 10; i++)
            std::cin >> ax[i] >> bx[i];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) std::cin >> w[i][j];

        dinic<int> d(n * n + n + 14);
        int s = 0, t = n * n + n + 12, sum = 0;
        for (int i = 1, id = 0; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                ++id;
                if (i == j) continue;
                d.add_edge(s, id, w[i][j]);
                sum += w[i][j];
                d.add_edge(id, n * n + i);
                d.add_edge(id, n * n + j);
            }
        }
        for (int i = 1; i <= n; i++) {
            int id = str[i - 1] - '0';
            d.add_edge(n * n + i, t, ax[id]);
            d.add_edge(n * n + i, n * n + n + id + 1);
        }
        for (int i = 0; i < 10; i++)
            d.add_edge(n * n + n + i + 1, t, bx[i] - ax[i]);
        std::cout << sum - d.max_flow(s, t) << "\n";
    }
}

